{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #变换的迷宫"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: escapeMaze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #变换的迷宫"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "某解密游戏中，有一个 N\\*M 的迷宫，迷宫地形会随时间变化而改变，迷宫出口一直位于 `(n-1,m-1)` 位置。迷宫变化规律记录于 `maze` 中，`maze[i]` 表示 `i` 时刻迷宫的地形状态，`\".\"` 表示可通行空地，`\"#\"` 表示陷阱。\n",
    "\n",
    "地形图初始状态记作 `maze[0]`，此时小力位于起点 `(0,0)`。此后每一时刻可选择往上、下、左、右其一方向走一步，或者停留在原地。\n",
    "\n",
    "小力背包有以下两个魔法卷轴（卷轴使用一次后消失）：\n",
    "+ 临时消除术：将指定位置在下一个时刻变为空地；\n",
    "+ 永久消除术：将指定位置永久变为空地。\n",
    "\n",
    "请判断在迷宫变化结束前（含最后时刻），小力能否在不经过任意陷阱的情况下到达迷宫出口呢？\n",
    "\n",
    "**注意： 输入数据保证起点和终点在所有时刻均为空地。**\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`maze = [[\".#.\",\"#..\"],[\"...\",\".#.\"],[\".##\",\".#.\"],[\"..#\",\".#.\"]]`\n",
    ">\n",
    ">输出：`true`\n",
    ">\n",
    ">解释：\n",
    "![maze.gif](https://pic.leetcode-cn.com/1615892239-SCIjyf-maze.gif)\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`maze = [[\".#.\",\"...\"],[\"...\",\"...\"]]`\n",
    ">\n",
    ">输出：`false`\n",
    ">\n",
    ">解释：由于时间不够，小力无法到达终点逃出迷宫。\n",
    "\n",
    "**示例 3：**\n",
    ">输入：`maze = [[\"...\",\"...\",\"...\"],[\".##\",\"###\",\"##.\"],[\".##\",\"###\",\"##.\"],[\".##\",\"###\",\"##.\"],[\".##\",\"###\",\"##.\"],[\".##\",\"###\",\"##.\"],[\".##\",\"###\",\"##.\"]]`\n",
    ">\n",
    ">输出：`false`\n",
    ">\n",
    ">解释：由于道路不通，小力无法到达终点逃出迷宫。\n",
    "\n",
    "**提示：**\n",
    "- `1 <= maze.length <= 100`\n",
    "- `1 <= maze[i].length, maze[i][j].length <= 50`\n",
    "- `maze[i][j]` 仅包含 `\".\"`、`\"#\"`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Db3wC1](https://leetcode.cn/problems/Db3wC1/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Db3wC1](https://leetcode.cn/problems/Db3wC1/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\".#.\",\"#..\"],[\"...\",\".#.\"],[\".##\",\".#.\"],[\"..#\",\".#.\"]]', '[[\".#.\",\"...\"],[\"...\",\"...\"]]', '[[\"....\",\"....\"],[\".#..\",\"#...\"],[\"..#.\",\".#..\"],[\"...#\",\"..#.\"],[\"....\",\".##.\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "        \n",
    "        time = len(maze)\n",
    "        nRow = len(maze[0])\n",
    "        nCol = len(maze[0][0])\n",
    "        \n",
    "        #理论最短时间也无法到达\n",
    "        if nCol+nRow-2>(time-1):\n",
    "            return False\n",
    "        \n",
    "        #初始未知和卷轴使用情况，0：未使用，1：只使用临时,2:只使用永久，3两者都用\n",
    "        record = (0, 0, 0)\n",
    "\n",
    "        #BFS\n",
    "        queue=deque()\n",
    "\n",
    "        queue.append(record)\n",
    "\n",
    "        #移动方向\n",
    "        directions=[[0,0],[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        \n",
    "        #用于记录使用过永久卷轴的位置\n",
    "        permanentSapce=set()\n",
    "\n",
    "        for i in range(1,time):\n",
    "            \n",
    "            states = len(queue)\n",
    "            \n",
    "            #记录本轮一访问的节点和对应的状态\n",
    "            visited = set()\n",
    "\n",
    "            for _ in range(states):\n",
    "\n",
    "                if len(queue)<=0:\n",
    "                    break\n",
    "\n",
    "                current=queue[0]\n",
    "                queue.popleft()\n",
    "\n",
    "                for move in directions:\n",
    "\n",
    "                    x=current[0]+move[0]\n",
    "                    y=current[1]+move[1]\n",
    "                   \n",
    "                    pos=(x,y) \n",
    "\n",
    "                    #到达终点\n",
    "                    if pos==(nRow-1,nCol-1):\n",
    "                        return True\n",
    "\n",
    "                    if pos[0]>=0 and pos[0]<nRow and pos[1]>=0 and pos[1]<nCol:\n",
    "                        \n",
    "                        #剩余时间类必定无法到达，剪枝\n",
    "                        minTime=nRow-1-x+nCol-1-y\n",
    "                        if minTime> time-i-1:\n",
    "                            continue \n",
    "                            \n",
    "                        if maze[i][pos[0]][pos[1]]==\".\":\n",
    "                            item=(*pos,current[-1])\n",
    "                            if item not in visited:\n",
    "                                visited.add(item)\n",
    "                                queue.append(item)\n",
    "                        #位置有陷阱\n",
    "                        else:\n",
    "                            \n",
    "                            #如果本位制曾被施加过永久卷轴，必定存在一个合法的状态。\n",
    "                            if (*pos,2) in permanentSapce:\n",
    "                                item=(*pos,2)\n",
    "                                if item not in visited:\n",
    "                                    visited.add(item)\n",
    "                                    queue.append(item)\n",
    "                            elif (*pos,3) in permanentSapce:\n",
    "                                item=(*pos,3)\n",
    "                                if item not in visited:\n",
    "                                    visited.add(item)\n",
    "                                    queue.append(item)\n",
    "                                \n",
    "                            #使用永久卷轴 \n",
    "                            if (current[-1]&2==0):\n",
    "                                item=(*pos,current[-1]|2)\n",
    "                                permanentSapce.add(item)\n",
    "                                if item not in visited:\n",
    "                                    visited.add(item)\n",
    "                                    queue.append(item)\n",
    "                            #使用临时卷轴\n",
    "                            if  (current[-1]&1)==0:\n",
    "                                item=(*pos,current[-1]|1)\n",
    "                                if item not in visited:\n",
    "                                    visited.add(item)\n",
    "                                    queue.append(item)\n",
    "                        \n",
    "\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dx = [0, 1, 0, -1, 0]\n",
    "        self.dy = [1, 0, -1, 0, 0]\n",
    "        self.visited = {}\n",
    "\n",
    "    def dfs(self, x, y, step, magic1, magic2, maze):\n",
    "        if (x, y, step, magic1, magic2) in self.visited:\n",
    "            return False\n",
    "        self.visited[(x, y, step, magic1, magic2)] = True\n",
    "\n",
    "        if x == self.n - 1 and y == self.m - 1:\n",
    "            return True\n",
    "        if step == self.max_step:\n",
    "            return False\n",
    "        if self.max_step - step < self.n - 1 - x + self.m - 1 - y:\n",
    "            return False\n",
    "        for i in range(5):\n",
    "            fx, fy = x + self.dx[i], y + self.dy[i]\n",
    "            if 0 <= fx < self.n and 0 <= fy < self.m:\n",
    "                if maze[step + 1][fx][fy] == '.':\n",
    "                    if self.dfs(fx, fy, step + 1, magic1, magic2, maze):\n",
    "                        return True\n",
    "                else:\n",
    "                    if not magic1 and self.dfs(fx, fy, step + 1, True, magic2, maze):\n",
    "                        return True\n",
    "                    if not magic2:\n",
    "                        for i in range(step + 1, self.max_step + 1):\n",
    "                            if self.dfs(fx, fy, i, magic1, True, maze):\n",
    "                                return True\n",
    "        return False\n",
    "\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "        self.n, self.m = len(maze[0]), len(maze[0][0])\n",
    "        self.max_step = len(maze) - 1\n",
    "        return self.dfs(0, 0, 0, False, False, maze)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\r\n",
    "        max_dep, n, m = len(maze), len(maze[0]), len(maze[0][0])\r\n",
    "        # 下一点移动方式\r\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1), (0, 0)]\r\n",
    "        # 记忆化搜索（为python缓存机制）\r\n",
    "        @lru_cache(None)\r\n",
    "        def dfs(x, y, dep, magic_a, magic_b):\r\n",
    "            # print(x, y, dep, magic_a, magic_b)\r\n",
    "            if x == n - 1 and y == m - 1:\r\n",
    "                return True\r\n",
    "            if dep + 1 == max_dep:\r\n",
    "                return False\r\n",
    "            # 剪枝\r\n",
    "            if n - 1 - x + m - 1 - y > max_dep - dep - 1:\r\n",
    "                return False\r\n",
    "            for i, j in dirs:\r\n",
    "                xx, yy = x + i, y + j\r\n",
    "                if xx < 0 or xx == n or yy < 0 or yy == m:\r\n",
    "                    continue\r\n",
    "                # 下一点为平地\r\n",
    "                if maze[dep + 1][xx][yy] == '.':\r\n",
    "                    if dfs(xx, yy, dep + 1, magic_a, magic_b):\r\n",
    "                        return True\r\n",
    "                # 下一点需要使用卷轴\r\n",
    "                else:\r\n",
    "                    if not magic_a:\r\n",
    "                        # 临时卷轴\r\n",
    "                        if dfs(xx, yy, dep + 1, True, magic_b):\r\n",
    "                            return True\r\n",
    "                    if not magic_b:\r\n",
    "                        # 用永久卷轴保持不动\r\n",
    "                        for next_dep in range(dep + 1, max_dep):\r\n",
    "                            if dfs(xx, yy, next_dep, magic_a, True):\r\n",
    "                                return True\r\n",
    "            return False\r\n",
    "        return dfs(0, 0, 0, False, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "        max_dep, n, m = len(maze), len(maze[0]), len(maze[0][0])\n",
    "        # 下一点移动方式\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1), (0, 0)]\n",
    "        # 记忆化搜索（为python缓存机制）\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y, dep, magic_a, magic_b):\n",
    "            # print(x, y, dep, magic_a, magic_b)\n",
    "            if x == n - 1 and y == m - 1:\n",
    "                return True\n",
    "            if dep + 1 == max_dep:\n",
    "                return False\n",
    "            # 剪枝\n",
    "            if n - 1 - x + m - 1 - y > max_dep - dep - 1:\n",
    "                return False\n",
    "            for i, j in dirs:\n",
    "                xx, yy = x + i, y + j\n",
    "                if xx < 0 or xx == n or yy < 0 or yy == m:\n",
    "                    continue\n",
    "                # 下一点为平地\n",
    "                if maze[dep + 1][xx][yy] == '.':\n",
    "                    if dfs(xx, yy, dep + 1, magic_a, magic_b):\n",
    "                        return True\n",
    "                # 下一点需要使用卷轴\n",
    "                else:\n",
    "                    if not magic_a:\n",
    "                        # 临时卷轴\n",
    "                        if dfs(xx, yy, dep + 1, True, magic_b):\n",
    "                            return True\n",
    "                    if not magic_b:\n",
    "                        # 用永久卷轴保持不动\n",
    "                        for next_dep in range(dep + 1, max_dep):\n",
    "                            if dfs(xx, yy, next_dep, magic_a, True):\n",
    "                                return True\n",
    "            return False\n",
    "        return dfs(0, 0, 0, False, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "        max_dep, n, m = len(maze), len(maze[0]), len(maze[0][0])\n",
    "        # 下一点移动方式\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1), (0, 0)]\n",
    "        # 记忆化搜索（为python缓存机制）\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y, dep, magic_a, magic_b):\n",
    "            # print(x, y, dep, magic_a, magic_b)\n",
    "            if x == n - 1 and y == m - 1:\n",
    "                return True\n",
    "            if dep + 1 == max_dep:\n",
    "                return False\n",
    "            # 剪枝\n",
    "            if n - 1 - x + m - 1 - y > max_dep - dep - 1:\n",
    "                return False\n",
    "            for i, j in dirs:\n",
    "                xx, yy = x + i, y + j\n",
    "                if xx < 0 or xx == n or yy < 0 or yy == m:\n",
    "                    continue\n",
    "                # 下一点为平地\n",
    "                if maze[dep + 1][xx][yy] == '.':\n",
    "                    if dfs(xx, yy, dep + 1, magic_a, magic_b):\n",
    "                        return True\n",
    "                # 下一点需要使用卷轴\n",
    "                else:\n",
    "                    if not magic_a:\n",
    "                        # 临时卷轴\n",
    "                        if dfs(xx, yy, dep + 1, True, magic_b):\n",
    "                            return True\n",
    "                    if not magic_b:\n",
    "                        # 用永久卷轴保持不动\n",
    "                        for next_dep in range(dep + 1, max_dep):\n",
    "                            if dfs(xx, yy, next_dep, magic_a, True):\n",
    "                                return True\n",
    "            return False\n",
    "        return dfs(0, 0, 0, False, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "        time = len(maze)\n",
    "        n, m = len(maze[0]), len(maze[0][0])\n",
    "        if n + m - 2 > time:\n",
    "            return False\n",
    "        best = [[[[float('inf'), -1] for i in range(2)] for k in range(m)] for j in range(n)]\n",
    "        record = [[[[float('inf')] * 2 for k in range(m)]\n",
    "                   for j in range(n)] for i in range(time)]\n",
    "        best[0][0][0][0] = 0\n",
    "        best[n - 1][m - 1][0][1] = time - 1\n",
    "        record[0][0][0][0] = int(maze[0][0][0] == '#')\n",
    "        record[time - 1][n - 1][m - 1][1] = int(maze[time - 1][n - 1][m - 1] == '#')\n",
    "        road = [(0, 0), (0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        z1 = [(0, 0, 0)]\n",
    "        z2 = [(time - 1, n - 1, m - 1)]\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < len(z1) or j < len(z2):\n",
    "            if i < len(z1):\n",
    "                t, x, y = z1[i]\n",
    "                if t < time:\n",
    "                    for a, b in road:\n",
    "                        o, p = x + a, y + b\n",
    "                        if -1 < o < n and -1 < p < m and n + m - o - p <= time - t:\n",
    "                            if not record[t][x][y][0] and max(best[o][p][0][1], best[o][p][1][1]) > t:\n",
    "                                return True\n",
    "                            if record[t][x][y][0] and best[o][p][0][1] > t:\n",
    "                                return True\n",
    "                            if maze[t + 1][o][p] == '#':\n",
    "                                if not record[t][x][y][0] and record[t + 1][o][p][0] > 1:\n",
    "                                    record[t + 1][o][p][0] = 1\n",
    "                                    z1.append((t + 1, o, p))\n",
    "                                    best[o][p][0][0] = min(best[o][p][0][0], t + 1)\n",
    "                            else:\n",
    "                                if record[t + 1][o][p][0] > record[t][x][y][0]:\n",
    "                                    now = record[t][x][y][0]\n",
    "                                    record[t + 1][o][p][0] = now\n",
    "                                    z1.append((t + 1, o, p))\n",
    "                                    best[o][p][now][0] = min(best[o][p][now][0], t + 1)\n",
    "            i += 1\n",
    "            if j < len(z2):\n",
    "                t, x, y = z2[j]\n",
    "                if t:\n",
    "                    for a, b in road:\n",
    "                        o, p = x + a, y + b\n",
    "                        if -1 < o < n and -1 < p < m and o + p <= t - 1:\n",
    "                            if not record[t][x][y][1] and min(best[o][p][0][0], best[o][p][1][0]) < t:\n",
    "                                return True\n",
    "                            if record[t][x][y][1] and best[o][p][0][0] < t:\n",
    "                                return True\n",
    "                            if maze[t - 1][o][p] == '#':\n",
    "                                if not record[t][x][y][1] and record[t - 1][o][p][1] > 1:\n",
    "                                    record[t - 1][o][p][1] = 1\n",
    "                                    z2.append((t - 1, o, p))\n",
    "                                    best[o][p][0][1] = max(best[o][p][0][1], t - 1)\n",
    "                            else:\n",
    "                                if record[t - 1][o][p][1] > record[t][x][y][1]:\n",
    "                                    now = record[t][x][y][1]\n",
    "                                    record[t - 1][o][p][1] = now\n",
    "                                    z2.append((t - 1, o, p))\n",
    "                                    best[o][p][now][1] = max(best[o][p][now][1], t - 1)\n",
    "            j += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "        time = len(maze)\n",
    "        n, m = len(maze[0]), len(maze[0][0])\n",
    "        if n + m - 2 > time:\n",
    "            return False\n",
    "        best = [[[[float('inf'), -1] for i in range(2)] for k in range(m)] for j in range(n)]\n",
    "        record = [[[[float('inf')] * 2 for k in range(m)]\n",
    "                   for j in range(n)] for i in range(time)]\n",
    "        best[0][0][0][0] = 0\n",
    "        best[n - 1][m - 1][0][1] = time - 1\n",
    "        record[0][0][0][0] = int(maze[0][0][0] == '#')\n",
    "        record[time - 1][n - 1][m - 1][1] = int(maze[time - 1][n - 1][m - 1] == '#')\n",
    "        road = [(0, 0), (0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        z1 = [(0, 0, 0)]\n",
    "        z2 = [(time - 1, n - 1, m - 1)]\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < len(z1) or j < len(z2):\n",
    "            if i < len(z1):\n",
    "                t, x, y = z1[i]\n",
    "                if t < time:\n",
    "                    for a, b in road:\n",
    "                        o, p = x + a, y + b\n",
    "                        if -1 < o < n and -1 < p < m and n + m - o - p <= time - t:\n",
    "                            if not record[t][x][y][0] and max(best[o][p][0][1], best[o][p][1][1]) > t:\n",
    "                                return True\n",
    "                            if record[t][x][y][0] and best[o][p][0][1] > t:\n",
    "                                return True\n",
    "                            if maze[t + 1][o][p] == '#':\n",
    "                                if not record[t][x][y][0] and record[t + 1][o][p][0] > 1:\n",
    "                                    record[t + 1][o][p][0] = 1\n",
    "                                    z1.append((t + 1, o, p))\n",
    "                                    best[o][p][0][0] = min(best[o][p][0][0], t + 1)\n",
    "                            else:\n",
    "                                if record[t + 1][o][p][0] > record[t][x][y][0]:\n",
    "                                    now = record[t][x][y][0]\n",
    "                                    record[t + 1][o][p][0] = now\n",
    "                                    z1.append((t + 1, o, p))\n",
    "                                    best[o][p][now][0] = min(best[o][p][now][0], t + 1)\n",
    "            i += 1\n",
    "            if j < len(z2):\n",
    "                t, x, y = z2[j]\n",
    "                if t:\n",
    "                    for a, b in road:\n",
    "                        o, p = x + a, y + b\n",
    "                        if -1 < o < n and -1 < p < m and o + p <= t - 1:\n",
    "                            if not record[t][x][y][1] and min(best[o][p][0][0], best[o][p][1][0]) < t:\n",
    "                                return True\n",
    "                            if record[t][x][y][1] and best[o][p][0][0] < t:\n",
    "                                return True\n",
    "                            if maze[t - 1][o][p] == '#':\n",
    "                                if not record[t][x][y][1] and record[t - 1][o][p][1] > 1:\n",
    "                                    record[t - 1][o][p][1] = 1\n",
    "                                    z2.append((t - 1, o, p))\n",
    "                                    best[o][p][0][1] = max(best[o][p][0][1], t - 1)\n",
    "                            else:\n",
    "                                if record[t - 1][o][p][1] > record[t][x][y][1]:\n",
    "                                    now = record[t][x][y][1]\n",
    "                                    record[t - 1][o][p][1] = now\n",
    "                                    z2.append((t - 1, o, p))\n",
    "                                    best[o][p][now][1] = max(best[o][p][now][1], t - 1)\n",
    "            j += 1\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "        time = len(maze)\n",
    "        n, m = len(maze[0]), len(maze[0][0])\n",
    "        if n + m - 2 > time:\n",
    "            return False\n",
    "        best = [[[[float('inf'), -1] for i in range(2)] for k in range(m)] for j in range(n)]\n",
    "        record = [[[[float('inf')] * 2 for k in range(m)]\n",
    "                   for j in range(n)] for i in range(time)]\n",
    "        best[0][0][0][0] = 0\n",
    "        best[n - 1][m - 1][0][1] = time - 1\n",
    "        record[0][0][0][0] = int(maze[0][0][0] == '#')\n",
    "        record[time - 1][n - 1][m - 1][1] = int(maze[time - 1][n - 1][m - 1] == '#')\n",
    "        road = [(0, 0), (0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        z1 = [(0, 0, 0)]\n",
    "        z2 = [(time - 1, n - 1, m - 1)]\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < len(z1) or j < len(z2):\n",
    "            if i < len(z1):\n",
    "                t, x, y = z1[i]\n",
    "                if t < time:\n",
    "                    for a, b in road:\n",
    "                        o, p = x + a, y + b\n",
    "                        if -1 < o < n and -1 < p < m and n + m - o - p <= time - t:\n",
    "                            if not record[t][x][y][0] and max(best[o][p][0][1], best[o][p][1][1]) > t:\n",
    "                                return True\n",
    "                            if record[t][x][y][0] and best[o][p][0][1] > t:\n",
    "                                return True\n",
    "                            if maze[t + 1][o][p] == '#':\n",
    "                                if not record[t][x][y][0] and record[t + 1][o][p][0] > 1:\n",
    "                                    record[t + 1][o][p][0] = 1\n",
    "                                    z1.append((t + 1, o, p))\n",
    "                                    best[o][p][0][0] = min(best[o][p][0][0], t + 1)\n",
    "                            else:\n",
    "                                if record[t + 1][o][p][0] > record[t][x][y][0]:\n",
    "                                    now = record[t][x][y][0]\n",
    "                                    record[t + 1][o][p][0] = now\n",
    "                                    z1.append((t + 1, o, p))\n",
    "                                    best[o][p][now][0] = min(best[o][p][now][0], t + 1)\n",
    "            i += 1\n",
    "            if j < len(z2):\n",
    "                t, x, y = z2[j]\n",
    "                if t:\n",
    "                    for a, b in road:\n",
    "                        o, p = x + a, y + b\n",
    "                        if -1 < o < n and -1 < p < m and o + p <= t - 1:\n",
    "                            if not record[t][x][y][1] and min(best[o][p][0][0], best[o][p][1][0]) < t:\n",
    "                                return True\n",
    "                            if record[t][x][y][1] and best[o][p][0][0] < t:\n",
    "                                return True\n",
    "                            if maze[t - 1][o][p] == '#':\n",
    "                                if not record[t][x][y][1] and record[t - 1][o][p][1] > 1:\n",
    "                                    record[t - 1][o][p][1] = 1\n",
    "                                    z2.append((t - 1, o, p))\n",
    "                                    best[o][p][0][1] = max(best[o][p][0][1], t - 1)\n",
    "                            else:\n",
    "                                if record[t - 1][o][p][1] > record[t][x][y][1]:\n",
    "                                    now = record[t][x][y][1]\n",
    "                                    record[t - 1][o][p][1] = now\n",
    "                                    z2.append((t - 1, o, p))\n",
    "                                    best[o][p][now][1] = max(best[o][p][now][1], t - 1)\n",
    "            j += 1\n",
    "        return False\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "        time = len(maze)\n",
    "        n, m = len(maze[0]), len(maze[0][0])\n",
    "        if n + m - 2 > time:\n",
    "            return False\n",
    "        best = [[[[float('inf'), -1] for i in range(2)] for k in range(m)] for j in range(n)]\n",
    "        record = [[[[float('inf')] * 2 for k in range(m)]\n",
    "                   for j in range(n)] for i in range(time)]\n",
    "        best[0][0][0][0] = 0\n",
    "        best[n - 1][m - 1][0][1] = time - 1\n",
    "        record[0][0][0][0] = int(maze[0][0][0] == '#')\n",
    "        record[time - 1][n - 1][m - 1][1] = int(maze[time - 1][n - 1][m - 1] == '#')\n",
    "        road = [(0, 0), (0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        z1 = [(0, 0, 0)]\n",
    "        z2 = [(time - 1, n - 1, m - 1)]\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < len(z1) or j < len(z2):\n",
    "            if i < len(z1):\n",
    "                t, x, y = z1[i]\n",
    "                if t < time:\n",
    "                    for a, b in road:\n",
    "                        o, p = x + a, y + b\n",
    "                        if -1 < o < n and -1 < p < m and n + m - o - p <= time - t:\n",
    "                            if not record[t][x][y][0] and max(best[o][p][0][1], best[o][p][1][1]) > t:\n",
    "                                return True\n",
    "                            if record[t][x][y][0] and best[o][p][0][1] > t:\n",
    "                                return True\n",
    "                            if maze[t + 1][o][p] == '#':\n",
    "                                if not record[t][x][y][0] and record[t + 1][o][p][0] > 1:\n",
    "                                    record[t + 1][o][p][0] = 1\n",
    "                                    z1.append((t + 1, o, p))\n",
    "                                    best[o][p][0][0] = min(best[o][p][0][0], t + 1)\n",
    "                            else:\n",
    "                                if record[t + 1][o][p][0] > record[t][x][y][0]:\n",
    "                                    now = record[t][x][y][0]\n",
    "                                    record[t + 1][o][p][0] = now\n",
    "                                    z1.append((t + 1, o, p))\n",
    "                                    best[o][p][now][0] = min(best[o][p][now][0], t + 1)\n",
    "            i += 1\n",
    "            if j < len(z2):\n",
    "                t, x, y = z2[j]\n",
    "                if t:\n",
    "                    for a, b in road:\n",
    "                        o, p = x + a, y + b\n",
    "                        if -1 < o < n and -1 < p < m and o + p <= t - 1:\n",
    "                            if not record[t][x][y][1] and min(best[o][p][0][0], best[o][p][1][0]) < t:\n",
    "                                return True\n",
    "                            if record[t][x][y][1] and best[o][p][0][0] < t:\n",
    "                                return True\n",
    "                            if maze[t - 1][o][p] == '#':\n",
    "                                if not record[t][x][y][1] and record[t - 1][o][p][1] > 1:\n",
    "                                    record[t - 1][o][p][1] = 1\n",
    "                                    z2.append((t - 1, o, p))\n",
    "                                    best[o][p][0][1] = max(best[o][p][0][1], t - 1)\n",
    "                            else:\n",
    "                                if record[t - 1][o][p][1] > record[t][x][y][1]:\n",
    "                                    now = record[t][x][y][1]\n",
    "                                    record[t - 1][o][p][1] = now\n",
    "                                    z2.append((t - 1, o, p))\n",
    "                                    best[o][p][now][1] = max(best[o][p][now][1], t - 1)\n",
    "            j += 1\n",
    "        return False\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "        time = len(maze)\n",
    "        n, m = len(maze[0]), len(maze[0][0])\n",
    "        if n + m - 2 > time:\n",
    "            return False\n",
    "        best = [[[[float('inf'), -1] for i in range(2)] for k in range(m)] for j in range(n)]\n",
    "        record = [[[[float('inf')] * 2 for k in range(m)]\n",
    "                   for j in range(n)] for i in range(time)]\n",
    "        best[0][0][0][0] = 0\n",
    "        best[n - 1][m - 1][0][1] = time - 1\n",
    "        record[0][0][0][0] = int(maze[0][0][0] == '#')\n",
    "        record[time - 1][n - 1][m - 1][1] = int(maze[time - 1][n - 1][m - 1] == '#')\n",
    "        road = [(0, 0), (0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        z1 = [(0, 0, 0)]\n",
    "        z2 = [(time - 1, n - 1, m - 1)]\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while i < len(z1) or j < len(z2):\n",
    "            if i < len(z1):\n",
    "                t, x, y = z1[i]\n",
    "                if t < time:\n",
    "                    for a, b in road:\n",
    "                        o, p = x + a, y + b\n",
    "                        if -1 < o < n and -1 < p < m and n + m - o - p <= time - t:\n",
    "                            if not record[t][x][y][0] and max(best[o][p][0][1], best[o][p][1][1]) > t:\n",
    "                                return True\n",
    "                            if record[t][x][y][0] and best[o][p][0][1] > t:\n",
    "                                return True\n",
    "                            if maze[t + 1][o][p] == '#':\n",
    "                                if not record[t][x][y][0] and record[t + 1][o][p][0] > 1:\n",
    "                                    record[t + 1][o][p][0] = 1\n",
    "                                    z1.append((t + 1, o, p))\n",
    "                                    best[o][p][0][0] = min(best[o][p][0][0], t + 1)\n",
    "                            else:\n",
    "                                if record[t + 1][o][p][0] > record[t][x][y][0]:\n",
    "                                    now = record[t][x][y][0]\n",
    "                                    record[t + 1][o][p][0] = now\n",
    "                                    z1.append((t + 1, o, p))\n",
    "                                    best[o][p][now][0] = min(best[o][p][now][0], t + 1)\n",
    "            i += 1\n",
    "            if j < len(z2):\n",
    "                t, x, y = z2[j]\n",
    "                if t:\n",
    "                    for a, b in road:\n",
    "                        o, p = x + a, y + b\n",
    "                        if -1 < o < n and -1 < p < m and o + p <= t - 1:\n",
    "                            if not record[t][x][y][1] and min(best[o][p][0][0], best[o][p][1][0]) < t:\n",
    "                                return True\n",
    "                            if record[t][x][y][1] and best[o][p][0][0] < t:\n",
    "                                return True\n",
    "                            if maze[t - 1][o][p] == '#':\n",
    "                                if not record[t][x][y][1] and record[t - 1][o][p][1] > 1:\n",
    "                                    record[t - 1][o][p][1] = 1\n",
    "                                    z2.append((t - 1, o, p))\n",
    "                                    best[o][p][0][1] = max(best[o][p][0][1], t - 1)\n",
    "                            else:\n",
    "                                if record[t - 1][o][p][1] > record[t][x][y][1]:\n",
    "                                    now = record[t][x][y][1]\n",
    "                                    record[t - 1][o][p][1] = now\n",
    "                                    z2.append((t - 1, o, p))\n",
    "                                    best[o][p][now][1] = max(best[o][p][now][1], t - 1)\n",
    "            j += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "       \n",
    "        #处理maze 可以不处理 处理完 0为可以走的 1为陷阱\n",
    "        def list2mat(l):\n",
    "            mat=[[0 for j in range(len(l[0]))]for i in range(len(l))]\n",
    "            \n",
    "            for i in range(len(mat)):\n",
    "                for j in range(len(mat[0])):\n",
    "                    if l[i][j]=='#':\n",
    "                        \n",
    "                        mat[i][j]=1\n",
    "                    else:\n",
    "                        mat[i][j]=0\n",
    "            return mat\n",
    "        mats=[]\n",
    "        for x in maze:\n",
    "            mats.append(list2mat(x))\n",
    "        #记忆化搜索 t是时间，i,j表示位置，u1，u2表示卷轴，c这个参数用于判断是否用了永久卷轴，由于dfs首先判断\n",
    "        #if u1==1 and u2==1 and mats[t][i][j]==1 所以c用来跳过这条判断执行后续的dfs\n",
    "        @lru_cache(None)\n",
    "        def dfs(t,i,j,u1,u2,c):\n",
    "            #判断是否达到条件或者参数出界\n",
    "            if t>=len(maze):\n",
    "                return False\n",
    "            if i<0 or i>=len(mats[0]) or j<0 or j>=len(mats[0][0]):\n",
    "                return False\n",
    "            ans=False\n",
    "            if c==True:\n",
    "                c=False\n",
    "                ans =ans or  dfs(t+1,i+1,j,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i-1,j,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j+1,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j-1,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j,u1,1,c)\n",
    "                return ans\n",
    "            if u1==1 and u2==1 and mats[t][i][j]==1:\n",
    "                return False\n",
    "        \n",
    "            if t<len(maze) and i==len(maze[0])-1 and j==len(maze[0][0])-1:\n",
    "                return True \n",
    "           \n",
    "            #使用一次卷轴\n",
    "            if mats[t][i][j]==1 and u1==0 :\n",
    "                ans =ans or  dfs(t+1,i+1,j,1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i-1,j,1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j+1,1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j-1,1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j,1,u2,c)\n",
    "            #使用永久卷轴\n",
    "            if mats[t][i][j]==1 and u2==0 : \n",
    "                ans =ans or  dfs(t+1,i+1,j,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i-1,j,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j+1,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j-1,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j,u1,1,c)\n",
    "                for k in range(t+2,len(mats)):\n",
    "                    ans =ans or  dfs(k,i+1,j,u1,1,c)\n",
    "                    ans =ans or  dfs(k,i-1,j,u1,1,c)\n",
    "                    ans =ans or  dfs(k,i,j+1,u1,1,c)\n",
    "                    ans =ans or  dfs(k,i,j-1,u1,1,c)\n",
    "                    ans =ans or  dfs(k,i,j,u1,1,c)\n",
    "            #不使用卷轴\n",
    "            if mats[t][i][j]==0 :\n",
    "                ans =ans or  dfs(t+1,i+1,j,u1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i-1,j,u1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j+1,u1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j-1,u1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j,u1,u2,c)\n",
    "            return ans\n",
    "        return dfs(0,0,0,0,0,False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "        self.T, self.n, self.m = len(maze), len(maze[0]), len(maze[0][0])\n",
    "        self.dxy = [(0, 1), (1, 0), (-1, 0), (0, -1), (0, 0)]\n",
    "\n",
    "        @functools.lru_cache(10000000)\n",
    "        def dfs(t, x, y, p0, p1) :\n",
    "            if x==self.n-1 and y==self.m-1 : return True\n",
    "            if t==self.T-1 : return False\n",
    "            for i, (dx, dy) in enumerate(self.dxy) :\n",
    "                tx, ty = x+dx, y+dy\n",
    "                tp1 = p1 if i==4 else min(1, p1)\n",
    "                if 0<=tx<self.n and 0<=ty<self.m :\n",
    "                    if maze[t+1][tx][ty]=='.' :\n",
    "                        if dfs(t+1, tx, ty, p0, tp1) : return True\n",
    "                    else :\n",
    "                        if p0==0 :\n",
    "                            if dfs(t+1, tx, ty, 1, tp1) : return True\n",
    "                        if p1==0 or (p1==2 and i==4) :\n",
    "                            if dfs(t+1, tx, ty, p0, 2) : return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0, 0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def escapeMaze(self, maze: List[List[str]]) -> bool:\n",
    "       \n",
    "        #处理maze 可以不处理 处理完 0为可以走的 1为陷阱\n",
    "        def list2mat(l):\n",
    "            mat=[[0 for j in range(len(l[0]))]for i in range(len(l))]\n",
    "            \n",
    "            for i in range(len(mat)):\n",
    "                for j in range(len(mat[0])):\n",
    "                    if l[i][j]=='#':\n",
    "                        \n",
    "                        mat[i][j]=1\n",
    "                    else:\n",
    "                        mat[i][j]=0\n",
    "            return mat\n",
    "        mats=[]\n",
    "        for x in maze:\n",
    "            mats.append(list2mat(x))\n",
    "        #记忆化搜索 t是时间，i,j表示位置，u1，u2表示卷轴，c这个参数用于判断是否用了永久卷轴，由于dfs首先判断\n",
    "        #if u1==1 and u2==1 and mats[t][i][j]==1 所以c用来跳过这条判断执行后续的dfs\n",
    "        @lru_cache(None)\n",
    "        def dfs(t,i,j,u1,u2,c):\n",
    "            #判断是否达到条件或者参数出界\n",
    "            if t>=len(maze):\n",
    "                return False\n",
    "            if i<0 or i>=len(mats[0]) or j<0 or j>=len(mats[0][0]):\n",
    "                return False\n",
    "            ans=False\n",
    "            if c==True:\n",
    "                c=False\n",
    "                ans =ans or  dfs(t+1,i+1,j,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i-1,j,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j+1,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j-1,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j,u1,1,c)\n",
    "                return ans\n",
    "            if u1==1 and u2==1 and mats[t][i][j]==1:\n",
    "                return False\n",
    "        \n",
    "            if t<len(maze) and i==len(maze[0])-1 and j==len(maze[0][0])-1:\n",
    "                return True \n",
    "           \n",
    "            #使用一次卷轴\n",
    "            if mats[t][i][j]==1 and u1==0 :\n",
    "                ans =ans or  dfs(t+1,i+1,j,1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i-1,j,1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j+1,1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j-1,1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j,1,u2,c)\n",
    "            #使用永久卷轴\n",
    "            if mats[t][i][j]==1 and u2==0 : \n",
    "                ans =ans or  dfs(t+1,i+1,j,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i-1,j,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j+1,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j-1,u1,1,c)\n",
    "                ans =ans or  dfs(t+1,i,j,u1,1,c)\n",
    "                for k in range(t+1,len(mats)):\n",
    "                    c=True\n",
    "                    ans =ans or  dfs(k,i,j,u1,1,c)\n",
    "            #不使用卷轴\n",
    "            if mats[t][i][j]==0 :\n",
    "                ans =ans or  dfs(t+1,i+1,j,u1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i-1,j,u1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j+1,u1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j-1,u1,u2,c)\n",
    "                ans =ans or  dfs(t+1,i,j,u1,u2,c)\n",
    "            return ans\n",
    "        return dfs(0,0,0,0,0,False)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
